/**
 * @file main.cpp
 * @author Fang Danyin <fdy20001205@163.com>
 * @brief 双链表的设计和实现
 * @date 2022-09-25
 * 
 */

#include <iostream>
#include <cstdlib>
#include <list>

template <typename Object>
class List
{
public:
    struct Node
    //定义节点
    {
        Object data;
        Node *prev;
        Node *next;
        
        Node(const Object & d =Object{}, Node *p = nullptr, Node *n = nullptr)
            :data{d}, prev{p}, next{ n }{ }
        Node(Object && d, Node * p = nullptr, Node * n = nullptr)
            :data{std::move( d )}, prev{p}, next{ n }{ }
    };
    
public:
    class const_iterator
    {
    public:
        const_iterator() : current{ nullptr }
            {}
        const Object & operator* () const //重载
            {return retrieve();}
        const_iterator & operator++ ()
        {
            current = current->next;
            return *this;    
        }

        const_iterator operator++( int )
        {
            const_iterator old = *this;
            ++( *this );
            return old;
        }

        bool operator==(const const_iterator & rhs) const
            {return current == rhs.current;}
        bool operator!=(const const_iterator & rhs) const
            {return !(*this == rhs);}

    public:
        /**
         * 存储一个指向当前节点的指针.
         */
        Node *current;
        Object & retrieve() const
            {return current->data;}
        const_iterator( Node *p ): current {p}
            {}
        
        friend class List<Object>;
    };


    class iterator : public const_iterator
    {
        public:
            iterator()
                {}
            Object & operator* ()
                {return const_iterator::retrieve();}
            const Object & operator* () const
                {return const_iterator::operator*();}
            
            iterator & operator++()
            {
                this->current = this->current->next;
                return *this;
            }

            iterator operator++(int)
            {
                iterator old = *this;
                ++( *this );
                return old;
            }

        public:
            iterator( Node *p ): const_iterator{ p } 
                { }
            
            friend class List<Object>;
    };

public:
    List()
        {init();}

    ~List()
    /**
     * 析构函数，回收头节点和尾节点.调用clear(),回收所有其他节点.
     */
    {
        clear();
        delete head;
        delete tail;
    }

    List( const List & rhs)
    /**
    * 拷贝复制函数.
    */
    {
        init();
        for( auto & x : rhs )
            push_back( x );
    }

    

    List & operator = (const List & rhs)
    {
        List copy = rhs;
        std::swap( *this, copy);
        return *this;
    }

    List( List && rhs )
        :theSize{ rhs.theSize}, head{ rhs.head }, tail{ rhs.tail } 
    {
        rhs.theSize = 0;
        rhs.head = nullptr;
        rhs.tail = nullptr;
    }

    List & operator= ( List && rhs)
    {
        std::swap( theSize, rhs.theSize );
        std::swap( head, rhs.head);
        std::swap( tail, rhs.tail);

        return *this;
    }

    void init()
    {
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next=tail;
        tail->prev=head;
    }

    iterator begin()
        {return { head->next};}
    const_iterator begin() const
        {return {head->next};}
    iterator end()
        {return {tail};}
    const_iterator end() const
        {return {tail};}
    
    int size() const
        {return theSize;}
    bool empty() const
        {return size()==0;}
    
    void clear()
    {
        while(!empty())
            pop_front();
    }
    Object & front()
        {return *begin();}
    const Object & front() const
        {return *begin();}
    Object & back()
        {return *--end();}
    const Object & back() const
       { return *--end();}
    void push_front( const Object & x )
        {insert( begin(), x );}
    void push_front( Object && x )
        {insert( begin(), std::move( x ) );}
    void push_back( const Object & x)
        {insert( end(), x );}
    void push_back( Object && x )
        {insert( end(), std::move( x ) );}
    void pop_front()
        {erase( begin() );}
    void pop_back()
        {erase(--end());}
    /**
    输出函数
     */
    void printList() const
        {
            for (Node* it = head->next ; it->next != nullptr; it = it->next)
                std::cout<< it->data <<"\t";
                std::cout<<"\b"<<std::endl;
        }

     //在itr前插入x
    iterator insert( iterator itr, const Object & x)
    {
        Node *p = itr.current;
        theSize++;
        return {p->prev = p->prev->next = new Node{ x, p->prev, p }};
    }
    

    //在itr前插入x
    iterator insert( iterator itr, Object && x)
    {
        Node *p = itr.current;
        theSize++;
        return {p->prev = p->prev->next = new Node{ std::move(x), p->prev, p }};
    }
    
    //删除在itr处的项

    iterator erase( iterator itr )
    {
        Node *p = itr.current;
        iterator retVal{ p->next };
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        theSize--;
        
        return retVal;
    }

    iterator erase( iterator from, iterator to ) //删除一段
    {
        for( iterator itr = from; itr != to; )
            itr = erase( itr );

            return to;
    }
    

    
public:
    int theSize;
    Node *head;
    Node *tail;


};

